/*
 * @lc app=leetcode.cn id=236 lang=swift
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */

class Solution236 {
    // 二叉树的最近公共祖先
    // 从某一个节点出发，左边找到了。右边也找到了。同时都不为nil,则此节点为最近公共祖先
    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
        guard let root = root else {
            return nil
        }
        if root === p || root === q {
            return root
        }
        let left = lowestCommonAncestor(root.left, p, q)
        let right = lowestCommonAncestor(root.right, p, q)
        if left != nil && right != nil {
            return root
        }
        if left != nil {
            return left
        }
        if right != nil {
            return right
        }
        return nil
    }
    static func test() {
        let solution = Solution236()
        let root = TreeNode()
        let p = TreeNode()
        let q = TreeNode()
        let r = solution.lowestCommonAncestor(root, p, q)
    }
}
// @lc code=end

